//  1 5 9 3 2 1 1
//->1       2 1 1

//思路：

//给出一个整数，从该整数中去掉k个数字，要求剩下的数字形成的新整数尽可能小。那么我们想到的是要使高位的数字降低，具体做法是把原整数的所有数字从左到右进行比较，如果发现某一位数字大于它右边的数字，那么在删除该数字后，必然会使该数位的值降低。每一步都要求得到删除一个数字后的最小值，经历k次，相当于求出了删除k个数字后的最小值。

//每一步都要求得到删除一个数字后的最小值，经历3次，相当于求出了删除k（k=3）个数字后的最小值。
//像这样依次求得局部最优解，最终得到全局最优解的思想，叫作贪心算法。”

/**
 * “运用了栈的特性，在遍历原整数的数字时，让所有数字一个一个入栈，当某个数字需要删除时，让该数字出栈。最后，程序把栈中的元素转化为字符串类型的结果。”
 * @param {*} num string  原整数
 * @param {*} k  number 删除数量
 */
function removeKDigits(num,k){
    // 新整数的最终长度 = 原整数长度-K
    let newLength = num.length-k;
    //  创建一个栈，用于接收原有的数字
    let stack = new Array(num.length);
    let top = 0;    
    for(let i=0;i<num.length;++i){
        // 遍历当前数字
        let c=num.charAt(i);
        // 当栈顶数字大于遍历到的当前数字时，栈顶数字出栈
        while(top>0 && stack[top-1]>c && k>0){
            top-=1;
            k-=1;
        }
        // 遍历到的当前数字入栈
        stack[top++]=c
        // console.log(stack)
    }
    // 找到栈中第1个非零数字的位置，构建新的输入 字符串
    let offset = 0;
    while(offset<newLength && stack[offset]=='0'){
        offset++;
    }
    return stack.slice(offset).join("");
}


console.log(removeKDigits("1593212",3))


// console.log(removeKDigits("541270936",3))